package org.lep.leetcode.graycode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Source : https://oj.leetcode.com/problems/gray-code/
 *
 * Created by lverpeng on 2017/8/3.
 *
 * The gray code is a binary numeral system where two successive values differ in only one bit.
 *
 * Given a non-negative integer n representing the total number of bits in the code,
 * print the sequence of gray code. A gray code sequence must begin with 0.
 *
 * For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
 *
 * 00 - 0
 * 01 - 1
 * 11 - 3
 * 10 - 2
 *
 * Note:
 * For a given n, a gray code sequence is not uniquely defined.
 *
 * For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
 *
 * For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
 */
public class GrayCode {

    /**
     * 将十进制（二进制）转换为格雷码
     *
     * 格雷码：wiki：https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81
     *
     * 二进制转格雷码的方法：
     * G：格雷码 B：二进制码
     * G(N) = (B(n)/2) XOR B(n)
     *
     * @param n 格雷码的位数
     * @return
     */
    public Integer[] binaryToGrayCode (int n) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < Math.pow(2, n); i++) {
            list.add(i >> 1 ^ i);
        }
        return list.toArray(new Integer[list.size()]);
    }


    public static void main(String[] args) {
        GrayCode grayCode = new GrayCode();
        System.out.println(Arrays.toString(grayCode.binaryToGrayCode(0)));
        System.out.println(Arrays.toString(grayCode.binaryToGrayCode(1)));
        System.out.println(Arrays.toString(grayCode.binaryToGrayCode(2)));
        System.out.println(Arrays.toString(grayCode.binaryToGrayCode(3)));
    }
}
